package com.formula.datastructure.exam.graph.sp;

import com.formula.datastructure.exercise.graph.undirect.MatrixGraph;

public class Floyd {

    public void getSP(MatrixGraph graph) {

        int N = graph.size;
        int[][] distance = graph.edges;
        int[][] prev = new int[N][N];

        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (distance[i][j] > distance[i][k] + distance[k][j]) {
                        distance[i][j] = distance[i][k] + distance[k][j];
                        prev[i][j] = k;
                    }
                }
            }
        }
        
    }
}
